import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class question_18 {
}
class Solution_18 {
    public List<List<Integer>> fourSum(int[] nums, int target) {

//        注意在java的int类型的数值的范围为-2,147,483,648 到 2,147,483,647（2^31）
        List<List<Integer>> resultList=new ArrayList<>();
//        第一部处理特殊的值,长度不够
        if(nums.length<4){
            return resultList;
        }
//        数组预处理
        Arrays.sort(nums);
//        使用暴力遍历外加双指针，下面分别表示for循环时每一层的原数组
        for (int i = 0; i < nums.length; i++) {
//            如果和上一步是重复的那么直接跳过，以防止出现重复的情况
            if(i-1>=0&&nums[i]==nums[i-1]){
                continue;
            }
//            现在
            for (int j = i+1; j <nums.length ; j++) {
                if(j-1>=i+1&&nums[j]==nums[j-1]){
                    continue;
                }
//              先计算还差多少
                int temp_targer=target-nums[i]-nums[j];
//                接下来使用双指针算法
                int l=j+1;
                int r=nums.length-1;
                while (true){
//                    两头的指针走到了一起，那么循环结束
                    if(l>=r){
                        break;
                    }

//                    左右指针如果和上一个对应的数值相同的话那么就跳过
                    if(l!=j+1&&nums[l]==nums[l-1]){
                        l++;
                        continue;
                    }
                    if(r!=nums.length-1&&nums[r]==nums[r+1]){
                        r--;
                        continue;
                    }
                    if (temp_targer<nums[l]+nums[r]) {
                        r--;
                        continue;
                    }else if(temp_targer>nums[l]+nums[r]){
                        l++;
                        continue;
                    }
//                   走到这一步说明相等哦
                    List<Integer> list=new ArrayList<>();
                    list.add(nums[i]);
                    list.add(nums[j]);
                    list.add(nums[l]);
                    list.add(nums[r]);
                    resultList.add(list);
//                    两头指针都要移动哦
                    l++;
                    r--;
                }
            }
        }
        return resultList;
    }

    public static void main(String[] args) {
        Solution_18 solution_18 = new Solution_18();
        int arr[]=new int[]{1,0,-1,0,-2,2};
        int targer=0;
        System.out.println(solution_18.fourSum(arr, targer));

    }
}
